// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.
//
// The representation of a DBImpl consists of a set of Versions.  The
// newest version is called "current".  Older versions may be kept
// around to provide a consistent view to live iterators.
//
// Each Version keeps track of a set of Table files per level.  The
// entire set of versions is maintained in a VersionSet.
//
// Version,VersionSet are thread-compatible, but require external
// synchronization on all accesses.

#ifndef STORAGE_LEVELDB_DB_VERSION_SET_H_
#define STORAGE_LEVELDB_DB_VERSION_SET_H_

#include <map>
#include <set>
#include <vector>

#include "db/dbformat.h"
#include "db/version_edit.h"
#include "port/port.h"
#include "port/thread_annotations.h"

namespace leveldb {

namespace log {
class Writer;
}

class Compaction;
class Iterator;
class MemTable;
class TableBuilder;
class TableCache;
class Version;
class VersionSet;
class WritableFile;

// Return the smallest index i such that files[i]->largest >= key.
// Return files.size() if there is no such file.
// REQUIRES: "files" contains a sorted list of non-overlapping files.
int FindFile(const InternalKeyComparator& icmp,
             const std::vector<FileMetaData*>& files, const Slice& key);

// Returns true iff some file in "files" overlaps the user key range
// [*smallest,*largest].
// smallest==nullptr represents a key smaller than all keys in the DB.
// largest==nullptr represents a key largest than all keys in the DB.
// REQUIRES: If disjoint_sorted_files, files[] contains disjoint ranges
//           in sorted order.
bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
                           bool disjoint_sorted_files,
                           const std::vector<FileMetaData*>& files,
                           const Slice* smallest_user_key,
                           const Slice* largest_user_key);

// Version表示当前的一个版本，该结构中会保存每个层级拥有的文件信息以及指向前一个和后一个版本的指针等。
// Version以双向链表的形式组织起来。
class Version {
 public:
  struct GetStats {  // 键查找时用来保存中间状态的一个结构
    FileMetaData* seek_file;  // 文件信息
    int seek_file_level;  // 文件所属的层级
  };

  // Append to *iters a sequence of iterators that will
  // yield the contents of this Version when merged together.
  // REQUIRES: This version has been saved (see VersionSet::SaveTo)
  // 将该版本的所有文件迭代器添加到迭代器列表中；
  void AddIterators(const ReadOptions&, std::vector<Iterator*>* iters);

  // Lookup the value for key.  If found, store it in *val and
  // return OK.  Else return a non-OK status.  Fills *stats.
  // REQUIRES: lock is not held
  Status Get(const ReadOptions&, const LookupKey& key, std::string* val,
             GetStats* stats);

  // Adds "stats" into the current state.  Returns true if a new
  // compaction may need to be triggered, false otherwise.
  // REQUIRES: lock is held
  // 更新该版本的统计信息，并返回是否需要进行compaction；
  bool UpdateStats(const GetStats& stats);

  // Record a sample of bytes read at the specified internal key.
  // Samples are taken approximately once every config::kReadBytesPeriod
  // bytes.  Returns true if a new compaction may need to be triggered.
  // REQUIRES: lock is held
  // 读取样本，返回是否需要进行compaction；
  bool RecordReadSample(Slice key);

  // Reference count management (so Versions do not disappear out from
  // under live iterators)
  void Ref();
  void Unref();

  // 获取与指定范围重叠的文件集合；
  void GetOverlappingInputs(
      int level,
      const InternalKey* begin,  // nullptr means before all keys
      const InternalKey* end,    // nullptr means after all keys
      std::vector<FileMetaData*>* inputs);

  // Returns true iff some file in the specified level overlaps
  // some part of [*smallest_user_key,*largest_user_key].
  // smallest_user_key==nullptr represents a key smaller than all the DB's keys.
  // largest_user_key==nullptr represents a key largest than all the DB's keys.
  // 检查指定level的文件集合是否与给定范围重叠；
  bool OverlapInLevel(int level, const Slice* smallest_user_key,
                      const Slice* largest_user_key);

  // Return the level at which we should place a new memtable compaction
  // result that covers the range [smallest_user_key,largest_user_key].
  // 决定新的memtable compaction输出文件的level；
  int PickLevelForMemTableOutput(const Slice& smallest_user_key,
                                 const Slice& largest_user_key);

  // 返回指定level的文件数目；
  int NumFiles(int level) const { return files_[level].size(); }

  // Return a human readable string that describes this version's contents.
  std::string DebugString() const;

 private:
  friend class Compaction;
  friend class VersionSet;

  class LevelFileNumIterator;

  explicit Version(VersionSet* vset)
      : vset_(vset),
        next_(this),
        prev_(this),
        refs_(0),
        file_to_compact_(nullptr),
        file_to_compact_level_(-1),
        compaction_score_(-1),
        compaction_level_(-1) {}

  Version(const Version&) = delete;
  Version& operator=(const Version&) = delete;

  ~Version();

  Iterator* NewConcatenatingIterator(const ReadOptions&, int level) const;

  // Call func(arg, level, f) for every file that overlaps user_key in
  // order from newest to oldest.  If an invocation of func returns
  // false, makes no more calls.
  //
  // REQUIRES: user portion of internal_key == user_key.
  void ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
                          bool (*func)(void*, int, FileMetaData*));

  VersionSet* vset_;  // 指向VersionSet对象的指针，表示该版本所属的VersionSet；
  Version* next_;     // 指向后一个Version的指针；
  Version* prev_;     // 指向前一个Version的指针；
  int refs_;          // 引用计数，表示当前有多少个迭代器正在引用该版本；

  // 二维数组，第一维为7个level，第二维为每个层级所包含的SSTable文件，每一个文件以一个FileMetaData结构表示。
  std::vector<FileMetaData*> files_[config::kNumLevels];

  // 下次需要进行Compaction操作的文件；
  FileMetaData* file_to_compact_;
  // 表示需要进行compaction的文件元数据所在的level；
  int file_to_compact_level_;

  // Level that should be compacted next and its compaction score.
  // Score < 1 means compaction is not strictly needed.  These fields
  // are initialized by Finalize().
  double compaction_score_;  // compact得分，表示当前版本对于compaction的需求程度，由Finalize()设置；如果compaction_score_大于1，说明需要进行一次Compaction操作。
  int compaction_level_;  // 表示应该在哪个level进行compaction，由Finalize()设置。
};

class VersionSet {
 public:
  VersionSet(const std::string& dbname, const Options* options,
             TableCache* table_cache, const InternalKeyComparator*);
  VersionSet(const VersionSet&) = delete;
  VersionSet& operator=(const VersionSet&) = delete;

  ~VersionSet();

  // Apply *edit to the current version to form a new descriptor that
  // is both saved to persistent state and installed as the new
  // current version.  Will release *mu while actually writing to the file.
  // REQUIRES: *mu is held on entry.
  // REQUIRES: no other thread concurrently calls LogAndApply()
  Status LogAndApply(VersionEdit* edit, port::Mutex* mu)
      EXCLUSIVE_LOCKS_REQUIRED(mu);

  // Recover the last saved descriptor from persistent storage.
  Status Recover(bool* save_manifest);

  // Return the current version.
  Version* current() const { return current_; }

  // Return the current manifest file number
  uint64_t ManifestFileNumber() const { return manifest_file_number_; }

  // Allocate and return a new file number
  uint64_t NewFileNumber() { return next_file_number_++; }

  // Arrange to reuse "file_number" unless a newer file number has
  // already been allocated.
  // REQUIRES: "file_number" was returned by a call to NewFileNumber().
  void ReuseFileNumber(uint64_t file_number) {
    if (next_file_number_ == file_number + 1) {
      next_file_number_ = file_number;
    }
  }

  // Return the number of Table files at the specified level.
  int NumLevelFiles(int level) const;

  // Return the combined file size of all files at the specified level.
  int64_t NumLevelBytes(int level) const;

  // Return the last sequence number.
  uint64_t LastSequence() const { return last_sequence_; }

  // Set the last sequence number to s.
  void SetLastSequence(uint64_t s) {
    assert(s >= last_sequence_);
    last_sequence_ = s;
  }

  // Mark the specified file number as used.
  void MarkFileNumberUsed(uint64_t number);

  // Return the current log file number.
  uint64_t LogNumber() const { return log_number_; }

  // Return the log file number for the log file that is currently
  // being compacted, or zero if there is no such log file.
  uint64_t PrevLogNumber() const { return prev_log_number_; }

  // Pick level and inputs for a new compaction.
  // Returns nullptr if there is no compaction to be done.
  // Otherwise returns a pointer to a heap-allocated object that
  // describes the compaction.  Caller should delete the result.
  Compaction* PickCompaction();

  // Return a compaction object for compacting the range [begin,end] in
  // the specified level.  Returns nullptr if there is nothing in that
  // level that overlaps the specified range.  Caller should delete
  // the result.
  Compaction* CompactRange(int level, const InternalKey* begin,
                           const InternalKey* end);

  // Return the maximum overlapping data (in bytes) at next level for any
  // file at a level >= 1.
  int64_t MaxNextLevelOverlappingBytes();

  // Create an iterator that reads over the compaction inputs for "*c".
  // The caller should delete the iterator when no longer needed.
  Iterator* MakeInputIterator(Compaction* c);

  // Returns true iff some level needs a compaction.
  bool NeedsCompaction() const {
    Version* v = current_;
    return (v->compaction_score_ >= 1) || (v->file_to_compact_ != nullptr);
  }

  // Add all files listed in any live version to *live.
  // May also mutate some internal state.
  void AddLiveFiles(std::set<uint64_t>* live);

  // Return the approximate offset in the database of the data for
  // "key" as of version "v".
  uint64_t ApproximateOffsetOf(Version* v, const InternalKey& key);

  // Return a human-readable short (single-line) summary of the number
  // of files per level.  Uses *scratch as backing store.
  struct LevelSummaryStorage {
    char buffer[100];
  };
  const char* LevelSummary(LevelSummaryStorage* scratch) const;

 private:
  class Builder;

  friend class Compaction;
  friend class Version;

  bool ReuseManifest(const std::string& dscname, const std::string& dscbase);

  void Finalize(Version* v);

  void GetRange(const std::vector<FileMetaData*>& inputs, InternalKey* smallest,
                InternalKey* largest);

  void GetRange2(const std::vector<FileMetaData*>& inputs1,
                 const std::vector<FileMetaData*>& inputs2,
                 InternalKey* smallest, InternalKey* largest);

  void SetupOtherInputs(Compaction* c);

  // Save current contents to *log
  Status WriteSnapshot(log::Writer* log);

  void AppendVersion(Version* v);

  Env* const env_;
  const std::string dbname_;
  const Options* const options_;
  TableCache* const table_cache_;
  const InternalKeyComparator icmp_;
  uint64_t next_file_number_;  // 下一个文件序列号
  uint64_t manifest_file_number_;  // Manifest文件的文件序列号
  uint64_t last_sequence_;  // 当前最大的写入序列号
  uint64_t log_number_;  // Log文件的文件序列号
  uint64_t prev_log_number_;  // 0 or backing store for memtable being compacted

  // Opened lazily
  WritableFile* descriptor_file_;
  log::Writer* descriptor_log_;
  Version dummy_versions_;  // Head of circular doubly-linked list of versions；Version的双向循环链表头，是一个无实际意义的Version对象，因此dummy_versions_的下一个Version是内存中保存的最旧的Version、dummy_versions_的上一个Version是最新的Version。
  Version* current_;        // == dummy_versions_.prev_； 指向链表中最新的Version

  // Per-level key at which the next compaction at that level should start.
  // Either an empty string, or a valid InternalKey.
  // levelDB一直在为每个level都维持一个string，里面存放该level上次compaction时的最大key值，
  // 里面的值代表每个层级下一次开始进行Compaction操作时需要从哪个键开始。
  std::string compact_pointer_[config::kNumLevels];
};

// A Compaction encapsulates information about a compaction.
class Compaction {
 public:
  ~Compaction();

  // Return the level that is being compacted.  Inputs from "level"
  // and "level+1" will be merged to produce a set of "level+1" files.
  // 返回被选择出来进行合并的level的值，比如n，那么就是将level n的文件与level n+1的文件进行merge。
  int level() const { return level_; }

  // Return the object that holds the edits to the descriptor done
  // by this compaction.
  VersionEdit* edit() { return &edit_; }

  // "which" must be either 0 or 1
  /* 
   * 返回input_[0]或者input_[1]这两个vector中存放的文件数量， 
   * input_[0]和input_[1]分别存放level n和level n+1参与merge的所有文件的FileMetaData指针
   */
  int num_input_files(int which) const { return inputs_[which].size(); }

  // Return the ith input file at "level()+which" ("which" must be 0 or 1).
  // 返回第which个输入文件集合中的第i个文件的FileMetaData，其中which取值为0或1，i表示文件在集合中的下标。
  FileMetaData* input(int which, int i) const { return inputs_[which][i]; }

  // Maximum size of files to build during this compaction.
  // 返回合并后生成的SSTable文件的最大大小，单位为字节。如果超过这个限制，则需要对生成的SSTable文件进行分割。
  uint64_t MaxOutputFileSize() const { return max_output_file_size_; }

  // Is this a trivial compaction that can be implemented by just
  // moving a single input file to the next level (no merging or splitting)
  // 判断该压缩操作是否可以被简单地实现为将一个输入文件移动到level+1层级中，而无需进行合并操作。
  /* 
   * 判断是否是简单的移动文件的情况，input[1]中没文件，input[0]只有一个文件，同时
   * grandparents_中有交集的文件总size小于配置值，这是为了避免创建的单个level+1文件后续merge到level+2时的高开销。
   * 必须在level层只有一个文件，且level + 1层没有文件，且leve+2层文件数小于配置的指定值才算简单压缩，否则都可能导致后续发生昂贵的合并操作.
   */ 
  bool IsTrivialMove() const;

  // Add all inputs to this compaction as delete operations to *edit.
  // 所有参与comapction的level/level+1文件都记录到set容器edit->deleted_files_，以便后续删除
  void AddInputDeletions(VersionEdit* edit);

  // Returns true if the information we have available guarantees that
  // the compaction is producing data in "level+1" for which no data exists
  // in levels greater than "level+1".
  // 如果user_key在大于level+1（大于level n+1，从level n+2开始)的level中并不存在的话，则返回true
  bool IsBaseLevelForKey(const Slice& user_key);

  // Returns true iff we should stop building the current output
  // before processing "internal_key".
  // 判断是否应该在处理完当前的internal_key之前停止生成输出。这个方法用于实现一些优化，例如避免生成不必要的重复数据。
  bool ShouldStopBefore(const Slice& internal_key);

  // Release the input version for the compaction, once the compaction
  // is successful.
  // 压缩成功后，释放输入文件所占用的资源，包括内存和磁盘空间等。
  void ReleaseInputs();

 private:
  friend class Version;
  friend class VersionSet;

  Compaction(const Options* options, int level);

  int level_;  // 被选择出来进行合并的level的值，比如n，那么就是将level n的文件与level n+1的文件进行merge。
  uint64_t max_output_file_size_;  // 表示生成的SSTable文件的最大大小，单位为字节。如果生成的SSTable文件大小超过了这个限制，则需要将其分割成多个小文件。
  Version* input_version_;  // 进行本次Compaction操作时的当前版本。
  VersionEdit edit_;  // 保存本次Compaction操作后的相关文件信息。VersionEdit对象保存了所有新增、删除和修改操作的信息。

  // Each compaction reads inputs from "level_" and "level_+1"
  // 保存需要被合并的两个输入文件集合，其中inputs_[0]表示属于level_层级的文件集合，inputs_[1]表示属于level_+1层级的文件集合，每个文件都用一个FileMetaData结构体指针表示。
  std::vector<FileMetaData*> inputs_[2];  // The two sets of inputs

  // State used to check for number of overlapping grandparent files
  // (parent == level_ + 1, grandparent == level_ + 2)
  // 保存祖先文件的元数据信息，即属于level_+2及以上层级的SSTable文件。
  // 记录所有与inputs_[0]和inputs_[1]并集的key有交集的level+2的文件放入grandparents_容器，这里获取level+2层的文件信息是为了后续在实际compaction过程生成level+1文件时保证新文件不会与level+2中太多文件有key range上的重合（导致后续level+1的compaction太多merge开销）。 
  std::vector<FileMetaData*> grandparents_;
  size_t grandparent_index_;  // Index in grandparent_starts_; 用于记录在压缩操作过程中已经处理过的祖先文件数量。
  bool seen_key_;             // Some output key has been seen; 用于记录当前输出的键值对是否已经被处理过。
  int64_t overlapped_bytes_;  // Bytes of overlap between current output; 用于记录当前输出的键值对是否已经被处理过。
                              // and grandparent files

  // State for implementing IsBaseLevelForKey

  // level_ptrs_ holds indices into input_version_->levels_: our state
  // is that we are positioned at one of the file ranges for each
  // higher level than the ones involved in this compaction (i.e. for
  // all L >= level_ + 2).
  size_t level_ptrs_[config::kNumLevels];  // 保存指向每一层级文件范围的指针，用于实现IsBaseLevelForKey方法。它是一个数组，其中第i个元素表示指向第i层级文件范围的指针。
};

}  // namespace leveldb

#endif  // STORAGE_LEVELDB_DB_VERSION_SET_H_
